// 动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。
// 既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。
// 动态规划就这么简单，就是穷举就完事了？我看到的动态规划问题都很难啊！
// 首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
// 而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。
// 另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。
// 以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，我来提供我研究出来的一个思维框架，辅助你思考状态转移方程：


// 明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。
// 下面通过斐波那契数列问题和凑零钱问题来详解动态规划的基本原理。前者主要是让你明白什么是重叠子问题（斐波那契数列严格来说不是动态规划问题），后者主要举集中于如何列出状态转移方程。
// 请读者不要嫌弃这个例子简单，只有简单的例子才能让你把精力充分集中在算法背后的通用思想和技巧上，而不会被那些隐晦的细节问题搞的莫名其妙。想要困难的例子，历史文章里有的是。

// 一、斐波那契数列
// 1、暴力递归
// 斐波那契数列的数学形式就是递归的，写成代码就是这样：
const fib = (N: number): number => {
  if (N == 1 || N == 2) return 1;
  return fib(N - 1) + fib(N - 2);
}

// 这个递归树怎么理解？就是说想要计算原问题 f(20)，我就得先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，我就要先算出子问题 f(18) 和 f(17)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。

// 递归算法的时间复杂度怎么计算？子问题个数乘以解决一个子问题需要的时间
// 子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。
// 解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。
// 所以，这个算法的时间复杂度为 O(2^n)，指数级别，爆炸。
// 观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如 f(18) 被计算了两次，而且你可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 f(18) 这一个节点被重复计算，所以这个算法及其低效。
// 这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。
// 2、带备忘录的递归解法
// 明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。
// 一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。

const fib2 = (N: number): number => {
  if (N < 1) return 0;
  // 备忘录全初始化为 0
  const memo: number[] = [];
  // 初始化最简情况
  return helperz(memo, N);
}

const helperz = (memo: number[], n: number): number => {
  if (n == 1 || n == 2) return 1;
  // 已经计算过
  if (memo[n] != 0) return memo[n];
  memo[n] = helperz(memo, n - 1) + helperz(memo, n - 2);
  return memo[n];
}

// 3、dp 数组的迭代解法

const fibn = (N: number) => {
  const dp: number[] = [];
  // base case
  dp[1] = dp[2] = 1;
  for (let i = 3; i <= N; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[N];
}

//这个例子的最后，讲一个细节优化。细心的读者会发现，根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：

const fibnn = (n: number) => {
  if (n == 2 || n == 1)
    return 1;
  let prev = 1, curr = 1;
  for (let i = 3; i <= n; i++) {
    let sum = prev + curr;
    prev = curr;
    curr = sum;
  }
  return curr;
}

// 二、凑零钱问题
// 比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
// 你认为计算机应该如何解决这个问题？显然，就是把所有肯能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。
// 1、暴力递归
// 首先，这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？你肯定不想看数学证明，我用一个直观的例子来讲解。
// 比如说，你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。
// 得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，“每门科目考到最高”这些子问题是互相独立，互不干扰的。
// 但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，此消彼长。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。
// 回到凑零钱问题，为什么说它符合最优子结构呢？比如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案，因为硬币的数量是没有限制的，子问题之间没有相互制，是互相独立的。
// 那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？
// 先确定「状态」，也就是原问题和子问题中变化的变量。由于硬币数量无限，所以唯一的状态就是目标金额 amount。
// 然后确定 dp 函数的定义：当前的目标金额是 n，至少需要 dp(n) 个硬币凑出该金额。
// 然后确定「选择」并择优，也就是对于每个状态，可以做出什么选择改变当前状态。具体到这个问题，无论当的目标金额是多少，选择就是从面额列表 coins 中选择一个硬币，然后目标金额就会减少：

//  伪码框架

const coinChange = (coins: number[], amount: number) => {
  // # 定义：要凑出金额 n，至少要 dp(n) 个硬币
  function dp(n: number) {
    // # 做选择，选择需要硬币最少的那个结果
    let res
    for (const coin of coins) {
      res = Math.min(res, 1 + dp(n - coin))
    }
    return res
  }
  return dp(amount)
}

// 最后明确 base case，显然目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1：
// 子问题总数为递归树节点个数，这个比较难看出来，是 O(n^k)，总之是指数级别的。每个子问题中含有一个 for 循环，复杂度为 O(k)。所以总时间复杂度为 O(k * n^k)，指数级别。
const coinChange1 = (coins: number[], amount: number) => {
  // # 定义：要凑出金额 n，至少要 dp(n) 个硬币
  function dp(n: number) {
    // base case
    if (n == 0) return 0
    if (n < 0) return -1
    // # 求最小值，所以初始化为正无穷
    let res = Infinity
    for (const coin of coins) {
      const subproblem = dp(n - coin)
      if (subproblem == -1) continue
      res = Math.min(res, 1 + subproblem)
    }

    return res != Infinity ? res : -1
  }
  return dp(amount)
}

// 2、带备忘录的递归
// 只需要稍加修改，就可以通过备忘录消除子问题：
// 不画图了，很显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。

const coinChange2 = (coins: number[], amount: number) => {
  // 备忘录
  const memo: { [key: number]: number } = {}
  function dp(n: number) {
    if (n in memo) return memo[n]

    if (n == 0) return 0
    if (n < 0) return -1
    let res = Infinity
    for (let coin of coins) {
      const subproblem = dp(n - coin)
      if (subproblem == -1) continue
      res = Math.min(res, 1 + subproblem)
    }
    memo[n] = res != Infinity ? res : -1
    return memo[n]
  }
  return dp(amount)
}

// 3、dp 数组的迭代解法
// 当然，我们也可以自底向上使用 dp table 来消除重叠子问题，dp 数组的定义和刚才 dp 函数类似，定义也是一样的：

const coinChange3 = (coins: number[], amount: number) => {
  const dp: number[] = Array(amount + 1)
  dp[0] = 0
  for (let i = 0; i < dp.length; i++) {

    // 内层 for 在求所有子问题 + 1 的最小值
    for (const coin of coins) {
      // 子问题无解，跳过
      if (i - coin < 0) continue;
      
      const dpi = dp[i] === undefined ? 0 : dp[i]
      const dpcoin = dp[i - coin] === undefined ? 0 : dp[i - coin]
      console.log(dp[i])
      dp[i] = Math.min(dpi, 1 + dpcoin);
    }
  }
  return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

console.log(coinChange3([1, 2, 5], 11))

